package ljl.alg.wangzheng_camp.round1.dp;

public class _62_paths {
    
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
    
    /**
     * 横竖一共是 m - 1 + n - 1 = m + n - 2 步
     * 随机挑选 m - 1 步
     * 总步数是 c(m - 1, m + n - 2)，咋算呢
     * (m + n - 2)!
     * ----------------
     * (m - 1)!(n - 1)!
     * */
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
    
    
}
